#include<bits/stdc++.h>
#define N 100
#define INF 0x3f3f3f3f
#define test

using namespace std;
int M[N][N];
int m,n;

int dist[N],P[N];
bool S[N];





void Init()
{
	cout<<"m: ";cin>>m;
	cout<<"n: ";cin>>n;

	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			M[i][j] = (i == j ? 0 : INF);
	cout<<"u v w"<<endl;
	for(int i = 0; i < m; i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		M[u][v] = w;
	}
#ifdef test
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			cout<<M[i][j]<<(j == n-1 ?'\n' :'\t');
		}
	}
#endif
	return;
}

void Dijkstra(int u,int v)
{
	//init
	for(int i = 0; i < n; i++)
		S[i] = false,P[i] = -1,dist[i] = INF;
	S[u] = true;
	dist[u] = 0;
	P[u] = u;
	//dist[s,v_i] <- w[s,v_i]
	for(int i = 0; i < n; i++)
		dist[i] = M[u][i],P[i] = (M[u][i] == INF?-1:u);

	for(int i = 1; i < n; i++)
	{
		//find min dist[s,v_j] from the set V-S
		int Min = INF,k;
		for(int j = 0; j < n; j++)
			if(!S[j] && Min > dist[j])
				Min = dist[j], k = j;
		//make v in S
		S[k] = true;
		for(int j = 0; j < n; j++)
		{
			if(!S[j] && dist[k] + M[k][j] < dist[j])
				dist[j] = dist[k] + M[k][j], P[j] = k;
		}

	}
#ifdef test
	cout<<"dist:"<<endl;
	for(int j = 0; j < n; j++)
		cout<<dist[j]<< (j == n-1?"\n":" ");
	cout<<"v:"<<endl;
	for(int j = 0; j < n; j++)
		cout<<P[j] <<(j == n-1 ? '\n':' ');
#endif //test
	printf("%d\n",dist[v]);
	stack<int>S;
	int temp = v;
	while(temp != u)
	{
		S.push(temp);
		temp = P[temp];
	}
	cout<<u<<"->";
	while(!S.empty())
	{
		cout<<S.top()<<"->";
		S.pop();
	}



	return ;
}


int main()
{
	Init();
	Dijkstra(0,n-1);

	return 0;
}
